package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

import java.util.LinkedList;

/**
 * LC513.找树左下角的值
 */
public class LC513 {
    private int deep = 0;
    private int leftValue = 0;
    public int findBottomLeftValue(TreeNode root) { //递归遍历
        leftValue = root.val;
        findLeftValue(root, 0);
        return leftValue;
    }

    private void findLeftValue(TreeNode root, int depth) {
        if (root.left == null && root.right == null) {
            if (depth > deep) {
                leftValue = root.val;
                deep = depth;
            }
        }
        if (root.left != null) {
            findLeftValue(root.left, depth + 1);
        }
        if (root.right != null) {
            findLeftValue(root.right, depth + 1);
        }
    }

    public int findBottomLeftValueC(TreeNode root) { //层序遍历
        LinkedList<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int ans = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = que.poll();
                if (i == 0) {
                    ans = poll.val;
                }
                if (poll.left != null) {
                    que.offer(poll.left);
                }
                if (poll.right != null) {
                    que.offer(poll.right);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        LC513 alg = new LC513();
        TreeNode root = new TreeNode(3, new TreeNode(9), new TreeNode(20));
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(alg.findBottomLeftValue(root));
    }
}
